/***尚硅谷Java数据结构与java算法                  ***/
/***https://www.bilibili.com/video/BV1E4411H73v ***/
/***八皇后问题  递归解法                         ***/
/***C++ 实现版本    written by Daniel           ***/
//在8*8的棋盘上，摆皇后，使其不在同一行、同一列，或者同一条斜线上
#include <iostream>
#include <cmath>
using std::cout;
using std::endl;
//以一个一维数组表示最后的结果；
//数组的第0行，代表棋牌第0行位置，依次类推...
const int MAX = 8;
void eightQueen(int *array, int size, int n);
bool isFit(int *array, int size, int n);
void printArray(int *array, int size);
static int count=0;
static int fitCount=0;
//
int main(int argc, char **argv)
{
	int *array = new int[MAX];
	for (int i = 0; i < MAX; i++) {
		array[i] = 0;
	}
	eightQueen(array, MAX, 0);
    cout<<"八皇后一共有"<<count<<"种解法"<<endl;
    cout<<"八皇后调用了"<<fitCount<<"次判断"<<endl;

	delete[] array;
	return 0;
}

void printArray(int *array, int size)
{
    count++;
	for (int i = 0; i < size; i++)
	{
		cout << array[i] << "\t";
	}
	cout << endl;
}
//功能：求解八皇后问题的函数
//参数：array 棋盘指针，
void eightQueen(int *array, int size, int n)
{
	//递归的终止条件，说明0-7行都满足条件
	if (n == size)
	{
		printArray(array, size);
		return;
	}
	for(int i=0;i<8;i++){
        array[n]=i;
        //如果满足这个条件，就进行对下一行 递归调用eightQueen();
        if (isFit(array,size,n))
        {
            eightQueen(array,size,n+1);
        }
        //如果不满足，  执行下一个循环  array[n]=i (i执行了依次++操作) 相当于在本行进行了回溯
        //如果本行操作都不满足，就会回到上一行for循环中的栈帧，执行array[n-1]=(i++)的操作
        //相当于进行了依次回溯
    }
}

bool isFit(int *array, int size, int n)
{
    fitCount++;
	for (int i = 0; i < n; i++)
	{
		//在同一数值线上，或者同一斜线上；返回false
		if (array[i] == array[n] || (abs(array[n] - array[i]) == abs(n - i)))
		{
			return false;
		}
	}
	return true;
}